package leetcode.listnode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。
 * <p>
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *  
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 * 示例 3：
 * <p>
 * 输入：head = [1,2,3,4,5], k = 1
 * 输出：[1,2,3,4,5]
 * 示例 4：
 * <p>
 * 输入：head = [1], k = 1
 * 输出：[1]
 * 提示：
 * <p>
 * 列表中节点的数量在范围 sz 内
 * 1 <= sz <= 5000
 * 0 <= Node.val <= 1000
 * 1 <= k <= sz
 */
public class ReverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        List<ListNode> list = new ArrayList<>(k);
        ListNode node = head;
        int index = 1;
        ListNode currentHead = null;
        ListNode currentTail;
        while (node != null) {
            list.add(node);
            node = node.next;
            if (index % k == 0){
                //判断开始位置
                if(currentHead == null){
                    head = list.get(list.size() - 1);
                }else{
                    currentHead.next = list.get(list.size() - 1);
                }
                currentHead = list.get(0);
                list.get(0).next = node;
                //对集合内的List调换位置
                for(int i = list.size() - 1;i > 0;i--){
                    list.get(i).next = list.get(i - 1);
                }
                list = new ArrayList<>(k);
            }
            index++;
        }
        return head;
    }

}
